#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;


//最大子数组和
//https://leetcode.cn/problems/maximum-subarray/
//class Solution {
//public:
//    int maxSubArray(vector<int>& nums) {
//        int n = nums.size();
//        if (n == 1) return nums[0];
//        vector<int> v(n);
//        int maxnum = v[0] = nums[0];
//        for (int i = 1; i < n; ++i)
//        {
//            v[i] = max(v[i - 1] + nums[i], nums[i]);
//            if (maxnum < v[i]) maxnum = v[i];
//        }
//        return maxnum;
//    }
//};
//优化空间复杂度O(1)
// class Solution {
// public:
//     int maxSubArray(vector<int>& nums) {
//         int n = nums.size();
//         int num = 0;
//         int maxnum = num = nums[0];
//         for(int i = 1;i<n;++i)
//         {
//             num = max(num+nums[i],nums[i]);
//             if(maxnum < num) maxnum = num;
//         }
//         return maxnum;
//     }
// };



// 环形子数组的最大和
// https://leetcode.cn/problems/maximum-sum-circular-subarray/
//class Solution {
//public:
//    int maxSubarraySumCircular(vector<int>& nums) {
//        int n = nums.size();
//        if (n == 1) return nums[0];
//
//        vector<int> maxv(n), minv(n);
//        int maxnum = 0;
//        int minnum = 0;
//        int sum = 0;
//        maxv[0] = minv[0] = maxnum = sum = nums[0];
//        for (int i = 1; i < n; ++i)
//        {
//            maxv[i] = max(maxv[i - 1] + nums[i], nums[i]);
//            minv[i] = min(minv[i - 1] + nums[i], nums[i]);
//            if (maxv[i] > maxnum) maxnum = maxv[i];
//            if (minv[i] < minnum) minnum = minv[i];
//            sum += nums[i];
//        }
//        if (sum == minnum) return maxnum; //如果nums中全为负数则sum会与minnum相等，此时直接返回maxnum即可
//        return max(maxnum, sum - minnum);
//    }
//};
//优化空间复杂度O(1)
// class Solution {
// public:
//     int maxSubarraySumCircular(vector<int>& nums) {
//         int n = nums.size();
//         if(n == 1) return nums[0];

//         int maxi = 0,mini = 0; //迭代值 迭代前进 记录上一个连续子数组的最大值和最小值
//         int maxnum = 0; //记录最大值
//         int minnum = 0; //记录最小值
//         int sum = 0;
//         maxi = mini = maxnum = minnum = sum = nums[0];
//         for(int i = 1;i<n;++i)
//         {
//             maxi = max(maxi+nums[i],nums[i]);
//             mini = min(mini+nums[i],nums[i]);
//             if(maxi > maxnum) maxnum = maxi;
//             if(mini < minnum) minnum = mini;
//             sum += nums[i]; //记录子数组和 如果连续子数组和在两边则中间是最小子数组和
//         }
//         if(sum == minnum) return maxnum; //如果nums中全为负数则sum会与minnum相等，此时直接返回maxnum即可
//         return max(maxnum,sum-minnum);
//     }
// };


//乘积最大子数组
//https://leetcode.cn/problems/maximum-product-subarray/submissions/
// class Solution {
// public:
//     int maxProduct(vector<int>& nums) {
//         int n = nums.size();
//         if(n == 1) return nums[0];
//         //f存第i个位置的最大值 g存第i个位置的最小值
//         vector<int> f(n),g(n);
//         //因为我们是从下标1开始，所以maxnum需要记录nums[0]的值
//         int maxnum = f[0] = g[0] = nums[0]; //f和g的初始值都为第一个数
        
//         for(int i = 1;i<n;++i)
//         {
//             //当nums>0时 最大值在f[i-1]的乘积中 如果nums<0 则最大值在g[i-1]的乘积中
//             f[i] = max(nums[i],max(f[i-1]*nums[i],g[i-1]*nums[i]));
//             //当nums>0时 最小值在g[i-1]的乘积中 如果nums<0 则最小值在f[i-1]的乘积中
//             g[i] = min(nums[i],min(f[i-1]*nums[i],g[i-1]*nums[i]));
//             if(f[i] > maxnum) maxnum = f[i];
//         }
//         return maxnum;
//     }
// };
//优化空间复杂度O(1)
// class Solution {
// public:
//     int maxProduct(vector<int>& nums) {
//         int n = nums.size();
//         if(n == 1) return nums[0];
//         //maxi表示当前位置的最大值 mini表示当前位置的最小值
//         int maxi = 0;
//         int mini = 0;
//         //因为我们是从下标1开始，所以maxnum需要记录nums[0]的值
//         int maxnum = maxi = mini = nums[0]; //f和g的初始值都为第一个数
        
//         for(int i = 1;i<n;++i)
//         {
//             int maxtmp = maxi; //因为mini的计算会用到maxi的上一次值 需要在maxi改变前保存值(保存谁取决于谁先计算)
//             //当nums>0时 最大值在maxi的乘积中 如果nums<0 则最大值在mini的乘积中
//             maxi = max(nums[i],max(maxi*nums[i],mini*nums[i]));
//             //当nums>0时 最小值在mini的乘积中 如果nums<0 则最小值在maxi的乘积中
//             mini = min(nums[i],min(maxtmp*nums[i],mini*nums[i]));
//             if(maxi > maxnum) maxnum = maxi;
//         }
//         return maxnum;
//     }
// };